package org.hot100.h146;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author yu
 * @Date 2022/8/10
 */
public class LRUCache4 {

    public static void main(String[] args) {

        LRUCache4 lruCache4 = new LRUCache4(2);
        lruCache4.put(1, 1);
        lruCache4.put(2, 3);
        lruCache4.put(2, 4);
        System.out.println(lruCache4.get(2));
    }

    Map<Integer, Node4> map = null;
    DoubleList4 doubleList = null;
    int length = 0;

    public LRUCache4(int length) {
        this.map = new HashMap<>();
        this.doubleList = new DoubleList4();
        this.length = length;
    }

    public void put(int k, int v) {
        Node4 node = new Node4(k, v);
        if (map.containsKey(k)) {
            Node4 temp = map.get(k);
            doubleList.remove(temp);
            doubleList.addFirst(temp);
            map.put(k, node);
        } else {
            if (doubleList.getSize() == length) {
                Node4 last = doubleList.removeLast();
                map.remove(last.k);
            }
            doubleList.addFirst(node);
            map.put(k, node);
        }
    }

    public int get(int k) {
        if (!map.containsKey(k)) {
            return -1;
        }
        int v = map.get(k).v;
        put(k, v);
        return v;
    }
}

class DoubleList4 {

    Node4 head, tail;
    int size = 0;

    public void addFirst(Node4 node) {
        if (head == null) {
            head = tail = node;
        } else {
            Node4 temp = head;
            node.next = temp;
            temp.prev = node;
            head = node;
        }
        size++;
    }

    public void remove(Node4 node) {
        if (node == head) {
            node.next.prev = null;
            head = node.next;
        }
        if (node == tail) {
            node.prev.next = null;
            tail = node.prev;
        }
        if (head == node && tail == node) {
            head = tail = null;
        }
        size--;
    }

    public Node4 removeLast() {
        Node4 node = tail;
        remove(tail);
        return node;
    }

    public int getSize() {
        return size;
    }
}

class Node4 {
    int k, v;
    Node4 prev, next;
    public Node4(int k, int v) {
        this.k = k;
        this.v = v;
    }
}